package 剑指offer;

public class 剑指Offer13机器人的运动范围 {
    int m;
    int n;
    boolean[][] visited;

    public static void main(String[] args) {
        剑指Offer13机器人的运动范围 o = new 剑指Offer13机器人的运动范围();
        System.out.println(o.movingCount(11,8,16));
        System.out.println(o.site(11, 11));
    }

    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.visited = new boolean[m][n];
        if (k == 0) return 1;//如果k等于0，机器人只能在[0,0]的位置
        return help(0, 0, k);
    }

    private int help(int i, int j, int k) {
        //终止条件,如果遇见了非法的位置，返回0；
        if (site(i, j) > k || i > m - 1 || j > n - 1 || i < 0 || j < 0 || visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;
        int res = 1 + help(i - 1, j, k) + help(i + 1, j, k) + help(i, j - 1, k) + help(i, j + 1, k);
        return res;
    }

    //计算位置的方法
    private int site(int i, int j) {
        int a = i / 100;
        int b = (i % 100) / 10;
        int c = i % 10;
        int d = j / 100;
        int e = (j % 100) / 10;
        int f = j % 10;
        return (a + b + c + d + e + f);

    }
}
